1. Technical Field
This invention relates generally to the field of data encryption and secure data storage. More specifically, this invention relates to computer-implemented mechanisms for encrypting data and storing data securely.
2. Description of the Related Art
A password authentication process determines whether a password (PWD) is valid for a particular user account (UID). Ideally such process should be designed and built in such a way that no passwords can ever be recovered therefrom, even, for example, when the corresponding system is breached completely and all program code and data thereof are stolen. This implies, foremost, that the password authentication system must not contain stored passwords. Presently, it is impossible to make any such system completely secure; however, there are ways to make it secure enough that breaches are difficult and attacking the system becomes impractical.
For purposes of understanding herein, a cryptographically secure hash function, sometimes referred to herein in brief as “hash function,” is a one-way function that maps any variable amount of input data into a fixed-size output value. For purposes of understanding herein, the output of the hash function applied to particular data is referred to as a digest of that data, or simply “digest.” When the input data to the hash function changes even a little bit, the resulting digest is completely different from the digest produced by applying the hash function to the unchanged input data.
It should be appreciated that while the hash function is considered effectively irreversible, i.e. that it is not possible to compute the original data from only its digest, there are other known ways by which the original data can be recovered. Thus, applying a hash function to data therefore may be considered only a first level of defense.
When the data to be hashed form a PWD, it is sometimes likely that many UIDs use identical PWDs that would therefore have the same digest. Such users may then be easy to identify as targets where an attacker, by compromising any one user, may then exploit more or all of such users. One way to prevent the same PWDs resulting in the same digest is to append a random string, referred to herein as a salt, to each password, before applying a hashing function. Thus, appending a unique random string to each PWD makes the input to the hash function unique and thereby avoids generating duplicate digests.
Rather than hashing the concatenation of a message and a salt to produce a digest, instead a keyed hash function takes the message and the salt as separate arguments or inputs. These two embodiments are equivalent and interchangeable. They differ mainly in that the keyed hash function usually combines the message and the key, or salt, in a way that is more rigorous than simply appending one to the other.
Presently, the above-described methodology is used commonly in password authentication systems and methods regarding computer security. For example, when creating a user account, the user is asked to enter a UID and a PWD. The password authentication process, upon receiving the UID and PWD, generates a unique salt, appends the salt to the PWD, and applies the hash function to the salted PWD to generate a digest. Such password authentication process then may store the UID, the salt, and the digest without ever storing the PWD, which may be discarded. Subsequently, when the user attempts to login, e.g. to access the password protected system, the user enters his or her UID and PWD to the password authentication system. The password authentication system attempts to authenticate the login by using the UID to retrieve the corresponding salt and digest. The password authentication system next appends the retrieved salt to the entered PWD and applies the hash function to this salted PWD to produce a new digest. The password authentication system then compares the new digest to the retrieved digest. When the new digest and the retrieved digest match, the PWD is valid, otherwise not.
It has been found that when trying to breach a login password authentication system, an attacker typically may first steal at least a portion of the stored UIDs, salts, and digests. On his own computer, the attacker then attempts to authenticate possible PWDs until the attacker finds at least one salted PWD that hashes to a stolen digest, perhaps using various shortcuts that make this brute force process more efficient.